<!DOCTYPE html>
<html>
  <head>
    <title>Numεrωmikωn</title>
    <link rel="stylesheet" href="../stock.css">
    <link rel="icon" type="image/x-icon" href="../favicon.ico">
    <meta content="text/html;charset=utf-8" http-equiv="Content-Type"/>
    <meta name="viewport" content="width=device-width, initial-scale=1" />
  </head>

  <body>
    <div class ="nav">
      <a href="../index">Indεχ</a>
      <a href="../clanky">Článκy</a>
      <a class="active" href="../googologie">Gωωgωlωgiε</a>
      <a href="../o_mne">Ω mně</a>
    </div>

    <div class="content-googology">
      <h1>Wainerova posloupnost ~ <i>f<sub>ω<sup>2</sup></sub>(n)</i></h1>

      <p>Doteď jsme používali Wainerovu fundamentální posloupnost ordinálů, ale nevíme, co přesně je. Seznámíme se s 
      mezními (limitními) ordinály a jak se mezi nimi přechází.</p>

      <p>Ordinál <i>α</i> je mezní ordinál, pokud jsou ordinály menší než <i>α</i> a zároveň kdykoliv je <i>β</i> menší než <i>α</i>, je ordinál <i>γ</i> takový, 
      aby platilo:</p>

      <div class="math"> 
        <p>β &lt γ &lt α</p>
      </div>

      <p>------</p>

      <p>Všechny ostatní ordinály jsou izolované. Jedinou výjimku tvoří <i>0</i>, jež není ani izolovaný ani mezní ordinál.</p>  

      <p>K tomuto popisu se můžeš kdykoliv vrátit, bude-li třeba, protože mu nemusíš nutně hned rozumět. Ukážeme si příklady
      mezních ordinálů, abychom je lépe pochopili. Začněme prvním nekonečným ordinálem, <i>ω</i>:</p>

      <div class="math"> 
        <p>ω = sup{0, 1, 2, 3, ...}</p>
      </div>

      <p>------</p>

      <p>Co to ale znamená? Suprémum je zde nejmenší ordinál, který je větší než všechny ostatní ordinály v množině. Jelikož přirozených čísel je nekonečno, 
      nenašli bychom největší číslo, ale můžeme si takto uměle stvořit nekonečné číslo.</p>

      <p>Abychom pokračovali dále, musíme si vysvětlit jedno pravidlo aritmetiky nekonečných ordinálů:</p>

      <div class="math"> 
        <p>1 + ω = ω</p>
        <p>ω + 1 ≠ ω</p>
        <p>1 + ω &lt ω + 1</p>
      </div>

      <p>------</p>

      <p>Na pořadí operací u nekonečných ordinálů záleží. Je nutné umístit větší prvky před menšími. Odůvodnění je jasné: kdybychom přidali prvek před <i>0</i>,
      mohli bychom přepsat tento prvek na <i>0</i> a všechna ostatní čísla zmenšit o <i>1</i>; množina by byla stejná. Ale přidáme-li tento prvek až po <i>ω</i>, 
      nic takového bychom udělat nemohli.</p>

      <p>Teď bychom tedy mohli pokračovat:</p>

      <div class="math">
        <p>ω * 2 = sup{ω + 0, ω + 1, ω + 2, ω + 3, ...}</p>
        <p>ω * 3 = sup{ω * 2 + 0, ω * 2 + 1, ω * 2 + 2, ω * 2 + 3, ...}</p>
      </div>

      <p>------</p>

      <p>Dostali bychom se až k:</p>

      <div class="math">
        <p>ω<sup>2</sup> = sup{ω * 0, ω * 1, ω * 2, ω * 3, ω * 4, ω * 5, ...}</p>
        <p>ω<sup>3</sup> = sup{ω<sup>2</sup> * 0, ω<sup>2</sup> * 1, ω<sup>2</sup> * 2, ω<sup>2</sup> * 3, ...}</p>
      </div>

      <p>------</p>

      <p>Můžeme tak vytvořit libovolný nekonečný ordinál:</p>

      <div class="math"> 
        <p>ω<sup>4</sup> * 5 = sup{ω<sup>4</sup> * 4 + 0, ω<sup>4</sup> * 4 + 1, ω<sup>4</sup> * 4 + 2, ...}</p>
      </div>

      <p>------</p>

      <p>Je načase zkusit mocninné věže:</p>

      <div class="math">
        <p>ω<sup>ω</sup> = sup{ω<sup>0</sup>, ω<sup>1</sup>, ω<sup>2</sup>, ω<sup>3</sup>, ω<sup>4</sup>, ...}</p>
        <p>ω<sup>ω<sup>ω</sup></sup> = sup{ω<sup>ω<sup>0</sup></sup>, ω<sup>ω<sup>1</sup></sup>, ω<sup>ω<sup>2</sup></sup>, ω<sup>ω<sup>3</sup></sup>, ...}</p>
      </div>

      <p>------</p>

      <p>Až bychom narazili na samotný konec Wainerovy hierarchie:</p>

      <div class="math"> 
        <p>ω<sup>ω<sup>ω<sup>ω (...)</sup></sup></sup> = ε<sub>0</sub></p>
      </div>

      <p>Tedy:</p>

      <div class="math"> 
        <p>ε<sub>0</sub> = sup{0, 1, ω, ω<sup>ω</sup>, ω<sup>ω<sup>ω</sup></sup>, ...}</p>
      </div>

      <p>------</p>

      <p><i>ε<sub>0</sub></i> je vrchol Wainerovy posloupnosti. Sestavili jsme si dobře uspořádanou řadu nekonečných ordinálů, které
      teď budeme moci využít s naší rychle rostoucí hierarchií. Kdykoliv narazíme na mezní ordinál, zaměníme jej za ntý prvek z naší
      fundamentální posloupnosti, již jsme použili v <i>sup{...}</i>. Pozor! Zde indexujeme prvky od <i>0</i>. Než ale 
      budeme pokračovat, je nezbytně nutné si celou posloupnost řádně zobecnit, jinak by se později mohly vyskytnout potíže:</p>

      <div class="math">
        <p>ω[n] = n</p>
        <p>ω<sup>α + 1</sup>[n] = ω<sup>α</sup> * n</p>
        <p>ω<sup>α</sup>[n] = ω<sup>α[n]</sup>, je-li α mezní ordinál</p>
        <p>(ω<sup>α<sub>1</sub></sup> + ω<sup>α<sub>2</sup></sub> + ... + ω<sup>α<sub>k</sub></sup>)[n] = ω<sup>α<sub>1</sup> + ... + ω<sup>α<sub>k</sub></sup>[n], pokud 
          α<sub>1</sub> ≥ α<sub>2</sub> ≥ ... ≥ α<sub>k</sub></p>
        <p>ε<sub>0</sub>[0] = 0</p>
        <p>ε<sub>0</sub>[n + 1] = ω<sup>ε<sub>0</sub>[n]</sup> = ω ↑↑ (n - 1)</p> 
      </div>

      <p>------</p>
      
      <p>Zkusme si jednoduchý příklad:</p>

      <div class="math"> 
        <p>f<sub>ω<sup>2</sup></sub>(3) = f<sub>ω * ω</sub>(3)</p>
      </div>

      <p>Užijeme třetí pravidlo rychle rostoucí hierarchie, abychom vyměnili mezní ordinál <i>ω * ω</i> za <i>ω * 3</i>, třetí
      prvek fundamentální posloupnosti pro <i>ω<sup>2</sup></i>:</p>

      <div class="math"> 
        <p>f<sub>ω * 3</sub>(3) = f<sub>ω * 2 + 3</sub>(3)</p>
      </div>

      <p>Co jsme to udělali? <i>ω * 3</i> je <i>ω + ω + ω</i>, ale to je taky mezní ordinál, takže poslední <i>ω</i> jsme opět nahradili trojkou. Stejně tak
      je i třetí prvek fundamentální posloupnosti pro <i>ω * 3</i> roven <i>ω * 2 + 3</i>. Pokračujme:</p>

      <div class="math"> 
        <p>f<sub>ω * 2 + 3</sub>(3) = f<sub>ω * 2 + 2</sub>(f<sub>ω * 2 + 2</sub>(f<sub>ω * 2 + 2</sub>(3)))</p>
      </div>

      <p>------</p>

      <p>To už začíná vypadat složitě! Zkusíme teď rozepisovat pouze nejvnořejnější části:</p>

      <div class="math"> 
        <p>f<sub>ω * 2 + 2</sub>(3) = ...(f<sub>ω * 2 + 1</sub>(3)))</p>
        <p>f<sub>ω * 2 + 1</sub>(3) = ...(f<sub>ω * 2</sub>(3)))</p>
        <p>f<sub>ω * 2</sub>(3) = f<sub>ω + 3</sub>(3)</p>
      </div>

      <p>Pozor! Jelikož <i>ω * 2</i> je mezní ordinál, museli jsme jej nejdřív přepsat podle třetího pravidla rychle rostoucí hierarcihe. Pokračujme:</p>

      <div class="math"> 
        <p>f<sub>ω + 3</sub>(3) = ...(f<sub>ω + 2</sub>(3)))</p>
        <p>f<sub>ω + 2</sub>(3) = ...(f<sub>ω + 1</sub>(3)))</p>
        <p>f<sub>ω + 1</sub>(3) = ...(f<sub>ω</sub>(3)))</p>
      </div>

      <p>Opět jsme narazili na mezní ordinál! Znovu jej přepišme:</p>

      <div class="math"> 
        <p>f<sub>ω</sub>(3) = f<sub>3</sub>(3)</p>
        <p>f<sub>3</sub>(3) = ...(f<sub>2</sub>(3)))</p>
        <p>f<sub>2</sub>(3) = ...(f<sub>1</sub>(3)))</p>
        <p>f<sub>1</sub>(3) = ...(f<sub>0</sub>(3)))</p>
      </div>

      <p>------</p>

      <p>Vůbec jen vypsat nejvnořenější funkce bylo obtížné! Pamatujeme si, že <i>f<sub>ω + 1</sub>(n)</i> roste podobně rychle jako Grahamovo
      <i>g<sub>n</sub></i> a že <i>f<sub>ω + 2</sub>(n)</i> rekurzivně opakuje <i>g<sub>n</sub></i>. Zkus si jen představit tu šílenost, kdybychom
      Grahamovo číslo použili v <i>ω + n</i> jako konečnou část indexu! A věř, že <i>f<sub>ω<sup>2</sup></sub>(3)</i> by se i takovému číslu
      mohlo pouze smát!</p>

      <p>Dále si ukážeme Hardyho hierarchii, abychom lépe porozuměli Goodsteinově větě. Brzo se i naučíme zkrotit rychle rostoucí hierarchii!</p>
    </div>

    <footer>
      <p class="footer"><a class="silent" href="https://creativecommons.org/licenses/by/4.0/" target="_blank">Kristian Tichota (CC-BY-4.0)</a></p>
    </footer>
  </body>
</html>
